package daliy;

import com.sun.nio.file.ExtendedWatchEventModifier;

import java.util.*;

public class Daily2 {

    private Map<Long,Long> map = new HashMap<>();

    private HashSet<Long> set = new HashSet<>();

    private int min = -1;

    {
        map.put(0L, 1L);
        set.add(1L);
        for(long i = 1; i <= 60; i++){
            map.put(i,map.get(i-1) * 2);
            set.add(map.get(i));
        }
    }
    //给你两个整数：num1 和 num2 。
    //
    //在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2i + num2 。
    //
    //请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。
    //
    //如果无法使 num1 等于 0 ，返回 -1
    public int makeTheIntegerZero(int num1, int num2) {
//        map.put(0L, 1L);
//        set.add(1L);
//        for(long i = 1; i <= 60; i++){
//            map.put(i,map.get(i-1) * 2);
//            set.add(map.get(i));
//        }
        returnBack(num1,num2,1);
        return min;
    }

    private int returnBack(long num1, long num2, int time){
        if(num1 - num2 < 1){
            return -1;
        }
        for(long i = 0; i <map.size(); i++){
            if(num2 < 0 && map.get(i) + num2 <= 0){
                continue;
            }
            if(set.contains(num1 - num2)){
                if(min == -1){
                    min = time;
                }else {
                    min = Math.min(min,time);
                }
                return time;
            }else {
                returnBack(num1 - num2 - map.get(i),num2,time + 1);
            }
        }
        return time;
    }


    // 1.测试函数
    public static void testMakeTheIntegerZero() {

        Daily2 solution = new Daily2();

        // 测试用例1: num1 = 3, num2 = -2
        // 3 - (2^1 + (-2)) = 3 - 0 = 3
        // 3 - (2^0 + (-2)) = 3 - (-1) = 4
        // 需要找到合适的组合使num1变为0
        int result1 = solution.makeTheIntegerZero(3, -2);
        System.out.println("Test 1 - Expected: 3, Actual: " + result1);

        // 测试用例2: num1 = 5, num2 = 0
        // 5 - (2^2 + 0) = 5 - 4 = 1
        // 1 - (2^0 + 0) = 1 - 1 = 0
        // 需要2步操作
        int result2 = solution.makeTheIntegerZero(5, 0);
        System.out.println("Test 2 - Expected: 2, Actual: " + result2);

        // 测试用例3: num1 = 2, num2 = 3
        // 2 - (2^i + 3) = 2 - (2^i + 3)
        // 由于2^i + 3 >= 4，而num1只有2，所以不可能完成
        int result3 = solution.makeTheIntegerZero(2, 3);
        System.out.println("Test 3 - Expected: -1, Actual: " + result3);

        // 测试用例4: num1 = 1, num2 = 1
        // 1 - (2^0 + 1) = 1 - 2 = -1
        // 无法完成
        int result4 = solution.makeTheIntegerZero(1, 1);
        System.out.println("Test 4 - Expected: -1, Actual: " + result4);
    }

    //「无零整数」是十进制表示中 不含任何 0 的正整数。
    //
    //给你一个整数 n，请你返回一个 由两个整数组成的列表 [a, b]，满足：
    //
    //a 和 b 都是无零整数
    //a + b = n
    //题目数据保证至少有一个有效的解决方案。
    //
    //如果存在多个有效解决方案，你可以返回其中任意一个
    public int[] getNoZeroIntegers(int n) {
        int[] res = new int[2];
        for(int i = 1; i < n; i++){
            if(hasZero(i)){
                continue;
            }
            if(hasZero(n - i)){
                continue;
            }
            res[0] = i;
            res[1] = n - i;
        }
        return res;
    }

    private boolean hasZero(int i){
        while (i >= 1){
            if(i % 10 == 0){
                return true;
            }
            i /= 10;
        }
        return false;
    }


    //在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
    //
    //给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：
    //
    //总共有 n 种语言，编号从 1 到 n 。
    //languages[i] 是第 i 位用户掌握的语言集合。
    //friendships[i] = [ui] 表示 ui 和 vi 为好友关系。
    //你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。
    //
    //请注意，好友关系没有传递性，也就是说如果 x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        HashMap<Integer, List<Integer>> friendShipMap = new HashMap<>();
        for (int[] friendship : friendships) {
            if(friendShipMap.containsKey(friendship[0])){
                List<Integer> friendList = friendShipMap.get(friendship[0]);
                friendList.add(friendship[1]);
            }else {
                ArrayList<Integer> friendList = new ArrayList<>();
                friendList.add(friendship[1]);
                friendShipMap.put(friendship[0],friendList);
            }
        }
        HashMap<Integer, Set<Integer>> languageMap = new HashMap<>();
        int j = 1;
        for (int[] language : languages) {
            HashSet<Integer> languageSet = new HashSet<Integer>();
            for (int i : language) {
                languageSet.add(i);
            }
            languageMap.put(j,languageSet);
            j++;
        }
        int res = 0;
        for (Map.Entry<Integer,List<Integer>> entry : friendShipMap.entrySet()){
            Set<Integer> myLanguage = languageMap.get(entry.getKey());
            for (Integer i : entry.getValue()) {
                Set<Integer> friendLanguage = languageMap.getOrDefault(i,Collections.emptySet());
                int temp = 1;
                for (Integer language : myLanguage) {
                    if(friendLanguage.contains(language)){
                        temp = 0;
                        break;
                    }
                }
                res += temp;
            }
        }
        return res;
    }

    public static void testMinimumTeachings() {
        Daily2 solution = new Daily2();

        // 测试用例1：所有人都能沟通，无需教学
        int[][] languages1 = {{1,2},{2,3},{3,4}};
        int[][] friendships1 = {{0,1},{1,2}};
        int result1 = solution.minimumTeachings(4, languages1, friendships1);
        System.out.println("Test 1 - 期望: 0, 实际: " + result1);

        // 测试用例2：需要教一门语言
        int[][] languages2 = {{1},{2},{3}};
        int[][] friendships2 = {{0,1},{1,2}};
        int result2 = solution.minimumTeachings(3, languages2, friendships2);
        System.out.println("Test 2 - 期望: 1, 实际: " + result2);

        // 测试用例3：部分用户已能沟通
        int[][] languages3 = {{1,2},{2},{1}};
        int[][] friendships3 = {{0,1},{1,2},{0,2}};
        int result3 = solution.minimumTeachings(2, languages3, friendships3);
        System.out.println("Test 3 - 期望: 1, 实际: " + result3);

        // 测试用例4：无好友关系
        int[][] languages4 = {{1},{2}};
        int[][] friendships4 = {};
        int result4 = solution.minimumTeachings(2, languages4, friendships4);
        System.out.println("Test 4 - 期望: 0, 实际: " + result4);
    }


    public static void main(String[] args) {
        testMinimumTeachings();
    }
}
